﻿// doubly_linked_list.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;

template<typename T>
class MyLinkedList {
public:
    MyLinkedList(){
        head = new Node(T());
        tail = new Node(T());
        head->next = tail;
        tail->prev = head;
        size = 0;

    }

    void addFirst(T val)
    {
        Node* new_node = new Node(val);
        Node* tmp = head->next;

        tmp->prev = new_node;
        head->next = new_node;

        new_node->prev = head;
        new_node->next = tmp;

        size++;
    }

    void addLast(T val)
    {
        Node* new_node = new Node(val);
        Node* tmp = tail->prev;

        tail->prev = new_node;
        tmp->next = new_node;

        new_node->prev = tmp;
        new_node->next = tail;

        size++;
    }

    void add(int index, T val)
    {
        if (!checkPosition(index)) throw out_of_range("add error: checkPosition fail");
        Node* new_node = new Node(val);
        Node* prev_node = head;
        for (int i = 0; i < index; i++)
        {
            prev_node = prev_node->next;
        }

        Node* next_node = prev_node->next;

        prev_node->next = new_node;
        next_node->prev = new_node;

        new_node->next = next_node;
        new_node->prev = prev_node;

        size++;
    }

    T removeFirst(){
        if (size == 0) throw out_of_range("error: list empty");

        Node* del_node = head->next;
        Node* next_node = del_node->next;
        T val = del_node->val;

        head->next = next_node;
        next_node->prev = head;

        delete del_node;

        size--;

        return val;
    }

    T removeLast(){
        if (size == 0) throw out_of_range("error: list empty");
    
        Node* del_node = tail->prev;
        Node* prev_node = del_node->prev;
        T val = del_node->val;

        tail->prev = prev_node;
        prev_node->next = tail;

        delete del_node;

        size--;

        return val;
    }

    T remove(int index){
        if (size == 0) throw out_of_range("error: list empty");

        if(!checkElement(index)) throw out_of_range("error: checkElement fail");
    
        if (index == 0) return removeFirst();
        if (index == size - 1) return removeLast();

        Node* prev_node = head;
        for (int i = 0; i < index; i++)
        {
            prev_node = prev_node->next;
        }

        Node* del_node = prev_node->next;
        Node* next_node = del_node->next;

        prev_node->next = next_node;
        next_node->prev = prev_node;

        T val = del_node->val;

        delete del_node;

        size--;

        return val;
    }


    T getFirst() {
        if (size == 0) throw out_of_range("getFirst Error: list empty");
        return head->next->val;
    }

    T getLast() {
        if (size == 0) throw out_of_range("getLast Error: list empty");
        return tail->prev->val;
    }

    T get(int index){
        Node* curr = getNode(index);

        return curr->val;
    }

    int getSize() { return size; }

private:
    // 虚拟头尾节点
    struct Node {
        T val;
        Node* prev;
        Node* next;
        Node(T value) :val(value), prev(nullptr), next(nullptr) {}
    };
    Node* head;
    Node* tail;
    int size;

    Node* getNode(int index)
    {
        if (!checkElement(index)) throw out_of_range("get Error: checkElement fail");

        Node* curr_node = head->next;
        for (int i = 0; i < index; i++)
        {
            curr_node = curr_node->next;
        }

        return curr_node;
    }

    bool checkElement(int index)
    {
        return index >= 0 && index < size;
    }

    bool checkPosition(int index)
    {
        return index >= 0 && index <= size;
    }
};


int main()
{
    MyLinkedList<int> list;
    list.addLast(1);
    list.addLast(2);
    list.addLast(3);
    list.addFirst(0);
    list.add(2, 100);

    cout << list.getFirst() << endl;
    cout << list.getLast() << endl;
    cout << list.get(1) << endl;

    cout << list.remove(1) << endl;
    //cout << list.removeFirst() << endl;
    //cout << list.removeLast() << endl;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
